package huffman;

import java.util.*;

public class HuffmanModel {
    static private class HuffmanNode implements Comparable<HuffmanNode> {
        HuffmanNode parent;
        HuffmanNode[] child;

        int data;
        int weight;
        int num;

        {
            child = new HuffmanNode[2];
        }

        public HuffmanNode(int i) {
            num = i;
            weight = 1;
        }

        public HuffmanNode(int i , int w) {
            this(i);
            weight = w;
        }

        public HuffmanNode(int i , int w, HuffmanNode[] child) {
            this(i, w);
            this.child[0] = child[0];
            this.child[1] = child[1];
        }

        public int compareTo(HuffmanNode node) {
            return this.weight - node.weight;
        }
    }

    private HuffmanNode root;
    private ArrayList<HuffmanNode> leaves;

    public HuffmanModel(int number) {
        leaves = createLeaves(number);
    }

    public void update(int i) {
        HuffmanNode node = leaves.get(i);
        HuffmanNode last = findLastInBlock(
    }

    public void printCode(int i) {
        StringBuilder s = new StringBuilder();
        HuffmanNode node = leaves.get(i);

        do {
            if (node.parent.child[0] == node) {
                s.append("0");
            }
            else {
                s.append("1");
            }

            node = node.parent;
        } while (node.parent != null);

        System.out.println(s.reverse().toString());
    }

    static private ArrayList<HuffmanNode> createLeaves(int num) {
        ArrayList<HuffmanNode> leaves = new ArrayList<HuffmanNode>(num);

        for (int i = 0; i < num; i++) {
            leaves.add(new HuffmanNode(i));
        }

        ArrayList<HuffmanNode> nodes = new ArrayList<HuffmanNode>(leaves);
        int nodesNumber = 2*num - 1;
        nodes.ensureCapacity(nodesNumber);

        initialize(nodes, num);

        return leaves;
    }

    static private void initialize(ArrayList<HuffmanNode> nodes, int index) {
        if (nodes.size() == 1)
            return;

        Collections.sort(nodes);

        HuffmanNode a = nodes.remove(0);
        HuffmanNode b = nodes.remove(0);

        HuffmanNode node = new HuffmanNode(index++, a.weight + b.weight, new HuffmanNode[] {a, b});
        a.parent = node;
        b.parent = node;

        nodes.add(node);

        initialize(nodes, index);
    }
}
